「NOIP 2021」方差

首先，这道题的std是$神奇DP+式子化简+观察类剪枝优化$极限过，但是我们还有另一种方法可以把这个题日过去

他就是模拟退火，观察到$n=1e4$并不是很大，再加上是寻找最优解的题目，所以可以考虑随机化算法模拟退火

可以想到初始使数列先减后增不会更劣，可以推得这样可以尽量让方差更小

观察到改变的方法其实就是改变两点的差分，我们可以把交换差分改为随机把一个差分插入到另一个地方

因此，我们每次可以随机一个值，并把它放到差分拐点的另一侧，使得差分序列仍然满足先减后增的性质

这样就可以日过去这道难紫DP了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair< int,int >
#define QWQ return 0;
#define reg register

const int N=1e4+10;

mt19937 r( time( 0 ) );

int n;
ll ans=1e18;
ll p[N], del[N];

ll F()
{
	ll sum=0, res=0;
	for( int i=2;i<=n;i++ ) p[i]=p[i-1]+del[i];
	for( int i=1;i<=n;i++ ) sum+=p[i];
	for( int i=1;i<=n;i++ ) res+=( p[i]*n-sum )*( p[i]*n-sum );
	return res/n;
}

void SA()
{
	double beginT=2e5, endT=1e5, T=0.9391;
	for( double t=beginT;t>endT;t*=T )
	{
		if( 1.0*clock()/CLOCKS_PER_SEC >= 0.999 )
			cout<<ans, exit( 0 );
		int x=r()%( n-1 )+2, y=r()%( n-1 )+2;
		swap( del[x],del[y] );
		ll f=F();
		if( f < ans ) ans=f;
		else if( exp( 1.0*( ans-f )/t ) <= exp( 1.0*r()/INT_MAX ) ) swap( del[x],del[y] );
	}
}

int main()
{
	freopen( "variance.in","r",stdin );
	freopen( "variance.out","w",stdout );
	ios::sync_with_stdio( false );
	cin.tie( nullptr ), cout.tie( nullptr );
	cin>>n;
	for( int i=1;i<=n;i++ )
		cin>>p[i],
		del[i]=p[i]-p[i-1];
	sort( del+2,del+n/2+1,greater< ll >() );
	sort( del+n/2+1,del+n+1 );
	while( 1 ) SA();
	QWQ
}